#include <iostream>
using namespace std;

struct node
{ int info;
  node *left;
  node *right;
};

node* maketree(int x, node* p, node *q)
{ node * r = new node;
  r->info = x;
  r->left = p;
  r->right = q;
  return r;
}

void preOrder(node * p)
{ if(p!=NULL)
  { cout << p->info << " ";
    preOrder(p->left);
    preOrder(p->right); 
  }
}

void inOrder(node * p)
{ if(p!=NULL)
  { inOrder(p->left);
    cout << p->info << " ";
    inOrder(p->right); 
  }
}

void postOrder(node * p)
{ if(p!=NULL)
  { postOrder(p->left);
    postOrder(p->right); 
    cout << p->info << " ";
  }
}

bool find(node *p, int x)
{ if(p==NULL) return false;
  if(x == p->info) return true;
  if(x < p->info) return find(p->left,x);
  return find(p->right,x);
}

void insert(node * &p, int x)
{ if(p==NULL)
  { p = new node;
    p->info = x;
    p->left = NULL;
    p->right = NULL;
    return;
  }
  if(x==p->info) return;
  if(x < p->info) insert(p->left,x);
  else insert(p->right,x);
}

node * & findpos(node * &p,int x)
{ if(p==NULL) return p;
  if(x == p->info) return p;
  if(x < p->info) return findpos(p->left,x);
  else return findpos(p->right,x);
}
/*
NodePtr& findPos(const Object & x,
NodePtr &p)
{ if(p==NULL) return p;
if(x == p->info) return p;
if(x < p->info)
return findPos(x,p->left);
else
return findPos(x,p->right);
}
*/
void remove(node * &p,int x)
{ node *q = findpos(p,x);
  cout << &q << " " << &p << endl;
  cout << q << " " << p << endl;
  if(q==NULL) return;
  q = NULL;
  
}


int main()
{ node * root = NULL;
  
  int x;
  do
  { inOrder(root);  cout << " L-K-D" << endl;   
    cout << "x = ";
    cin >> x;
    insert(root,x);
  } while(x>0);
  
  do
  { inOrder(root);  cout << " L-K-D" << endl;   
    cout << "x = ";
    cin >> x;
    remove(root,x);
  } while(x>0);
  

  return 0;
}
